Programmable logic devices, such as field-programmable gate arrays (“FPGAs”) and complex programmable logic devices (“CPLDs”) have a variety of resources, such as logic, memory, input/output (I/O”) interfaces, and routing fabric that can be configured to perform various user-defined operations. Generally, the routing fabric connects sources and destinations together. For example, a block of memory might be connected through a portion of the routing fabric to a configurable logic block, and another portion of the routing fabric might connect the logic block or the memory block to an I/O interface. The routing fabric is essentially a matrix of wires (also called “nodes”) and user-selectable (programmable) switches (called “arcs” for purposes of this patent application), that are usually transistors. These transistors allow multiple configurations of the routing fabric, unlike anti-fuse or other types of one-time-programmable switches. Other terms used to describe arcs are programmable interconnect points (“PIPs”), muxes, or simply switches. The routing fabric is implemented as multi-level multiplexers, and each arc represents a path through a mux or set of muxes.
A path between a source and a destination is defined by selecting a sequence of arcs to connect a series of nodes. A typical FPGA might have on the order of one million arcs. This leads to a large number of possible routes through the fabric. A user of the FPGA typically designs an application that is placed and routed on the physical FPGA design. The FPGA manufacturer typically has no knowledge of how the user design will utilize the arcs and nodes of the routing fabric, and thus it is important for the manufacturer to insure that all arcs are valid. In other words, to insure that all arcs operate as expected to selectively connect nodes when the FPGA is configured.
The time required to test all arcs in a physical FPGA is substantial and costly. As the complexity of FPGAs has increased, some devices may exceed the capacity of the test tool (test station) to fully exercise all arcs in a single test sequence.